package leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

@SuppressWarnings("all")
public class _56_合并区间 {
    // 有若干个区间 intervals = [[1,3],[2,6],[8,10],[15,18]]
    // 将重叠的区间合并，例如区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
    // 最终合并的结果为 [[1,6],[8,10],[15,18]]
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
            return null;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        ArrayList<int[]> resultList = new ArrayList<>();
        // 区间A的右边界包含在区间B的范围内就说明着两个区间可以合并
        for (int i = 0; i < intervals.length; i++) {
            // 数组左右边界
            int left = intervals[i][0];
            int right = intervals[i][1];
            // 以当前集合为参照，向数组区间进行逐一合并，思路更加清晰

            // 如果当前区间和下一个区间没有交集，那么就单独添加下一个区间
            if (resultList.size() == 0 || resultList.get(resultList.size() - 1)[1] < left) {
                resultList.add(new int[]{left, right});
            } else {
                // 当前区间和下一个区间有交集，即需要合并区间，重要的是思考怎么合并，区间合并实际上就是当前区间的左边界不变，右边界变大
                // 更新当前区间的右边界，达到合并的效果
                resultList.get(resultList.size() - 1)[1] = Math.max(resultList.get(resultList.size() - 1)[1], right);
            }
        }
        // 返回和当前集合大小的数组
        return resultList.toArray(new int[resultList.size()][]);
    }
}
